1102. Задача с палочками

 

Хуанхан имеет n палочек разной длины. Однажды она положила их в ряд, длины которых равны s1, s2, s3, ..., sn. После измерения длины каждой палочки sk (1 ≤ k ≤ n), она обнаружила что для некоторых палочек si и sj (1 ≤ i < j ≤ n) длина каждой палочки расположенной между si и sj, больше si и меньше sj.

По заданным длинам s1, s2, s3, ...sn найдите наибольшее значение j – i.

 

Вход. Состоит из нескольких тестов. Каждый тест состоит из двух строк. Первая строка содержит количество палочек n (n ≤ 50000). Вторая строка содержит n различных натуральных чисел (не больших 105) – длины палочек.

 

Выход. Выведите наибольшее значение j – i для каждого теста в отдельной строке. Если не существует таких i и j, то выведите -1.

 

Пример входа

Пример выхода

4

5 4 3 6

4

6 5 4 3

9

12 4 8 7 5 9 6 3 1

1

-1

4

 

 

 

РЕШЕНИЕ

RMQ + бинарный поиск

 

Анализ алгоритма

Для каждого индекса i находим максимальный индекс k (i ≤ k ≤ n), для которого RMinQ(si+1, …, sk) > si, бинарным поиском. Искомым j будет индекс, на котором достигается RMaxQ(si, …, sk) (i ≤ j ≤ k).

Таким образом следует для каждого индекса i найти максимальный возможный индекс j и среди всех таких пар (i, j) вычислить максимальную разность j – i.

 

Пример

Рассмотрим третий пример.

Пусть i = 2 (s2 = 4). Наибольшим является индекс k = 7, для которого RMinQ(si+1, …, sk) > 4. RMaxQ(s3, …, s7) достигается на индексе j = 6.

 

Реализация алгоритма

 

#include <cstdio>

#include <algorithm>

#define MAX 50010

#define LOGMAX 16

using namespace std;

 

int dp_max[MAX][LOGMAX], dp_min[MAX][LOGMAX];

int a[MAX];

int i, j, n, res;

 

void Build_RMQ_Array(int *b)

{

  int i, j;

  for (i = 1; i <= n; i++)

  {

    dp_min[i][0] = b[i];

    dp_max[i][0] = i;

  }

 

  for (j = 1; 1 << j <= n; j++)

    for (i = 1; i + (1 << j) - 1 <= n; i++)

    {

      if (b[dp_max[i][j - 1]] > b[dp_max[i + (1 << (j - 1))][j - 1]])

        dp_max[i][j] = dp_max[i][j - 1];

      else

        dp_max[i][j] = dp_max[i + (1 << (j - 1))][j - 1];

 

      dp_min[i][j] =

        min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);

    }

}

 

int RangeMaxQuery(int i, int j)

{

  int k = 0;

  while ((1 << (k + 1)) <= j - i + 1) k++;

 

  if (a[dp_max[i][k]] > a[dp_max[j - (1<<k) + 1][k]])

    return dp_max[i][k];

  else

    return dp_max[j - (1<<k) + 1][k];

}

 

int RangeMinQuery(int i, int j)

{

  int k = 0;

  while ((1 << (k + 1)) <= j - i + 1) k++;

  return min(dp_min[i][k],dp_min[j - (1<<k) + 1][k]);

}

 

int BinSearch(int Left, int Right)

{

  int MinValue = a[Left++];

  if (RangeMinQuery(Left,Right) > MinValue) return Right;

 

  while (Right > Left)

  {

    int Middle = (Left + Right) / 2;

    if (RangeMinQuery(Left,Middle) > MinValue)

      Left = Middle + 1;

    else

      Right = Middle;

  }

 

  if (dp_min[Left][0] <= MinValue) Left--;

  return Left;

}

 

int main(void)

{

  while(scanf("%d",&n) == 1)

  {

    for(i = 1; i <= n; i++) scanf("%d",&a[i]);

 

    Build_RMQ_Array(a);

    res = 0;

 

    for(i = 1; i <= n; i++)

    {

      j = BinSearch(i, n);

      j = RangeMaxQuery(i,j);

      if (j - i > res) res = j - i;

    }

    if (res == 0) res = -1;

    printf("%d\n",res);

  }

  return 0;

}